package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/4 19:37
 * @Describe 迷宫的最短路径
 * 题目描述：
 * 给定一个二维数组表示迷宫，0 表示可以通行的路径，1 表示墙或者障碍物，
 * 求从起点 (0, 0) 到终点 (n-1, m-1) 的最短路径。
 *
 * 代码说明：
 * DIRECTIONS 数组：用来表示四个方向的移动：上、下、左、右。
 * 队列 queue：用于 BFS 中存储当前要扩展的节点位置。
 * 布尔数组 visited：用于记录每个位置是否已经访问过，避免重复遍历。
 * BFS 的流程：
 * 初始时，将起点 (0, 0) 加入队列。
 * 每次从队列中取出一个位置，检查其四周的合法位置，若为可通行的路径且未访问，则加入队列。
 * 如果到达终点 (n-1, m-1)，返回当前步数作为最短路径。
 * 如果队列为空且未能到达终点，则说明迷宫不可达，返回 -1。
 */
import java.util.LinkedList;
import java.util.Queue;

public class MazeSolver {

    // 四个方向：上、下、左、右
    private static final int[][] DIRECTIONS = {
            {0, 1},  // 右
            {1, 0},  // 下
            {0, -1}, // 左
            {-1, 0}  // 上
    };

    public static int shortestPath(int[][] maze) {
        int n = maze.length;
        int m = maze[0].length;

        // 特殊情况：如果起点或者终点是墙，直接返回 -1
        if (maze[0][0] == 1 || maze[n - 1][m - 1] == 1) {
            return -1;
        }

        // 队列中存储的是位置坐标 (x, y)
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];  // 用来标记已经访问的节点

        // 初始化：从起点 (0, 0) 开始
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        // 记录当前步数
        int steps = 0;

        // 开始广度优先搜索（BFS）
        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;  // 每一层遍历，步数增加

            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];

                // 如果到达终点，返回步数
                if (x == n - 1 && y == m - 1) {
                    return steps;
                }

                // 向四个方向扩展
                for (int[] direction : DIRECTIONS) {
                    int newX = x + direction[0];
                    int newY = y + direction[1];

                    // 判断新坐标是否合法且未访问过
                    if (newX >= 0 && newX < n && newY >= 0 && newY < m &&
                            maze[newX][newY] == 0 && !visited[newX][newY]) {
                        queue.offer(new int[]{newX, newY});
                        visited[newX][newY] = true;  // 标记为已访问
                    }
                }
            }
        }

        // 如果无法到达终点，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 1, 0},
                {1, 1, 0, 1, 0},
                {0, 0, 0, 0, 0}
        };

        int result = shortestPath(maze);
        if (result != -1) {
            System.out.println("迷宫的最短路径长度是: " + result);
        } else {
            System.out.println("无法到达终点！");
        }
    }
}

